import java.util.HashMap;
import java.util.Map;

/**
 * 两数之和
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
 * 你可以按任意顺序返回答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author wengzhengkai
 */
public class TwoSum {

    /**
     * 双层 for 循环暴力遍历法，时间复杂度为 O(N^2)，空间复杂度为 O(1)
     */
    public static int[] twoSumByDoubleFor(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    /**
     * 使用 HashMap 的 key 和 value 分别存放数组的值及下标，
     * 假设 x 为遍历数组时取到的当前元素，若碰到 key 值等于 target - x 则说明满足条件，即刻返回；
     * 时间复杂度为 O(N)，只需遍历一次数组；
     * 空间复杂度为 O(N)，使用 HashMap 来存放数组的每个元素值及下标。
     */
    public static int[] twoSumByHashMap(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }
        Map<Integer, Integer> numMap = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            int another = target - nums[i];
            if (numMap.containsKey(another)) {
                return new int[]{numMap.get(another), i};
            }
            numMap.put(nums[i], i);
        }
        return new int[0];
    }
}
